package com.future;

import com.future.util.ListNode;

import java.util.Comparator;
import java.util.PriorityQueue;

import static com.future.util.CommonUtil.printListNode;

/**
 * 给你一个链表数组，每个链表都已经按升序排列。
 * <p>
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 */
public class Solution_mergeKLists_23 {

    /**
     * 输入：lists = [[1,4,5],[1,3,4],[2,6]]
     * 输出：[1,1,2,3,4,4,5,6]
     *
     * @param args
     */
    public static void main(String[] args) {
        ListNode head1 = new ListNode(1, new ListNode(4, new ListNode(5)));
        ListNode head2 = new ListNode(1, new ListNode(3, new ListNode(4)));
        ListNode head3 = new ListNode(2, new ListNode(6));
        ListNode[] lists = {head1, head2, head3};
        ListNode listNode = mergeKLists(lists);
        printListNode(listNode);

    }

    public static ListNode mergeKLists(ListNode[] lists) {
        if (null == lists || lists.length == 1) {
            return null;
        } else if (lists.length < 2) {
            return lists[0];
        }
        //
        PriorityQueue<ListNode> queue = new PriorityQueue<>(new NodeComparator());
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                queue.offer(lists[i]);
            }
        }
        // 返回节点
        ListNode resNode = new ListNode(-1);
        // 操作节点
        ListNode opNode = resNode;
        while (queue != null && queue.size() > 0) {
            // 每一次把最小的链表头结点弹出来，注意这里是弹出来（拿出来，且移除掉）
            ListNode curr = queue.poll();
            opNode.next = curr;
            // 移动
            opNode = opNode.next;
            if (curr != null && curr.next != null) {
                // 把链表下个节点继续放入优先队列
                queue.offer(curr.next);
            }
        }
        return resNode.next;
    }

    /**
     * 链表，需要自定义比较器
     */
    static class NodeComparator implements Comparator<ListNode> {
        @Override
        public int compare(ListNode o1, ListNode o2) {
            if (o1.val < o2.val) {
                return -1;
            }
            return 1;
        }
    }
}
